package com.gxc.linkedList;

/**
 *  删除排序链表中的重复元素 II
 * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
 */
public class DeleteDuplicates {

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode newH = new ListNode(-200);
        newH.next = head;

        ListNode prev = newH;
        ListNode cur = head;
        ListNode next = cur.next;
        while (next != null) {
            while (next != null && cur.val == next.val) {
                cur = cur.next;
                next = cur.next;
            }

            if (cur != prev.next) {
                cur.next = null;
                prev.next = next;
                if (next != null) cur = prev.next;
                if (next != null) next = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
                next = cur.next;
            }
        }
        return newH.next;
    }

    public ListNode deleteDuplicates2(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode dummy = new ListNode(0, head);

        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return dummy.next;
    }

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

}
